package leetcode_core.leetcode_6;

import java.util.ArrayList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月12日 18:42
 */


public class PathSum {
    class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
          }
    }

    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        backtrack(root,targetSum,new ArrayList<>());
        return ans;
    }
    private void backtrack(TreeNode root,int targetSum,List<Integer> path){
        if(root == null){
            return ;
        }
        targetSum = targetSum - root.val;
        path.add(root.val);
        //做出选择
        if(root.left == null && root.right == null && targetSum == 0){
            ans.add(new ArrayList<>(path));
            return ;
        }
        //递归回溯
        backtrack(root.left,targetSum,path);
        backtrack(root.right,targetSum,path);
        //撤销选择
        path.remove(path.size()-1);
    }
}
